# -*- coding: utf-8 -*-

"""
    Time    : 2020/12/15 上午10:20
    Author  : Thinkgamer
    File    : 406-根据身高重建队列.py
    Software: PyCharm
    Desc    : https://leetcode-cn.com/problems/queue-reconstruction-by-height/
"""
"""
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。


示例 1：
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：
输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示：

1 <= people.length <= 2000
0 <= hi <= 106
0 <= ki < people.length
题目数据确保队列可以被重建
"""


"""
	v1 思路：对数据进行降序排序，第一个元素相同时，第二个元素升序排序
			这样数组的中元素的第二个值即表示该元素应该在新数组中的位置，然后对应位置的元素及后边的元素，依次往后瞬移一位
	v2 思路：和v1一致，只不过是优化了一下代码，保证while 内的循环次数小一些
"""
# 484 ms 9.35% ｜ 13.6 MB 43.79%
def reconstruct_queue_v1(people):
	people.sort(key=lambda k: [k[0], -k[1]], reverse=True)
	new_arr = [people[0]] * len(people)
	for one in people[1:]:
		ind = one[1]
		# 将 ind 位置及之后的元素都往后串 1 位，再将 one 赋值 给 ind 位置的值
		i = len(people) - 1
		while i > ind:
			new_arr[i] = new_arr[i-1]
			i -= 1
		new_arr[ind] = one
	return new_arr


# 188 ms 24.81% ｜ 13.9 MB 5.10%
def reconstruct_queue_v2(people):
	people.sort(key=lambda k: [k[0], -k[1]], reverse=True)
	new_arr = [people[0]]
	for one in people[1:]:
		new_arr.append(one)
		ind = one[1]
		# 将 ind 位置及之后的元素都往后串 1 位，再将 one 赋值 给 ind 位置的值
		i = len(new_arr) - 1
		while i > ind:
			new_arr[i] = new_arr[i - 1]
			i -= 1
		new_arr[ind] = one
	return new_arr


# people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
people = [[6, 0], [5, 0], [4, 0], [3, 2], [2, 2], [1, 4]]
result = reconstruct_queue_v2(people)
print(result)